package algorithm.middle;

import java.util.HashSet;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-03-21 20:27
 * @Description: 73. 矩阵置零
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 * 进阶：
 *
 *     一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 *     一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 *     你能想出一个仅使用常量空间的解决方案吗？
 *输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：[[1,0,1],[0,0,0],[1,0,1]]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/set-matrix-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SetZeroes73 {
    //二维数组 矩阵
    public static void main(String[] args) {
        int[][] arr =   {{0,1,2,0},
                        {3,4,5,2},
                        {1,3,1,5}};
        setZeroes(arr);
    }

    public static void setZeroes(int[][] matrix) {
        HashSet<Integer> hang = new HashSet<>();
        HashSet<Integer> lie = new HashSet<>();
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j] == 0){
                    hang.add(i);
                    lie.add(j);
                }
            }
        }
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix.length;j++){
                if (hang.contains(i)||lie.contains(j)){
                    matrix[i][j]=0;
                }
            }
        }
    }

    /**
     * 我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 000。这样，
     * 第一列的第一个元素即可以标记第一行是否出现 000。但为了防止第一列的第一个元素被提前更新，
     * 我们需要从最后一行开始，倒序地处理矩阵元素
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/set-matrix-zeroes/solution/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param matrix
     */
    public void 官方题解(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }

}
